//
//  BinarySearchTree.swift
//  Chapter3LinkedList
//
//  Created by TRS-Mobile on 2021/9/1.
//

import Foundation

struct BinarySearchTree<E: Comparable> {
    private(set) var root: BinaryNode<E>?
    init() {}
    
    mutating func insert(_ value: E) {
        root = insert(from: root, value: value)
    }
    
    private func insert(from node: BinaryNode<E>?, value: E) -> BinaryNode<E> {
        guard let node = node else { return BinaryNode(value: value) }
        if value < node.value {
            node.leftChild = insert(from: node.leftChild, value: value)
        }else {
            node.rightChild = insert(from: node.rightChild, value: value)
        }
        return node
    }
    
    func contains(_ value: E) -> Bool {
//        guard let root = root else { return false }
//        var found = false
//        root.traverseInOrder {
//            if $0 == value {
//                found = true
//            }
//        }
//        return found
        
        var current = root
        while let node = current {
            if node.value == value {
                return true
            }
            if value < node.value {
                current = node.leftChild
            }else {
                current = node.rightChild
            }
        }
        return false
    }
    
    mutating func remove(_ value: E) {
        root = remove(node: root, value: value)
    }
    
    private func remove(node: BinaryNode<E>?, value: E) -> BinaryNode<E>? {
        guard let node = node else { return .none }
        if value == node.value {
            if node.leftChild == nil && node.rightChild == nil {
                return .none
            }
            if node.leftChild == nil {
                return node.rightChild
            }
            if node.rightChild == nil {
                return node.leftChild
            }
            node.value = node.rightChild!.min.value
            node.rightChild = remove(node: node.rightChild, value: node.value)
        } else if value < node.value {
            node.leftChild = remove(node: node.leftChild, value: value)
        } else {
            node.rightChild = remove(node: node.rightChild, value: value)
        }
        return node
    }
}

extension BinarySearchTree: CustomStringConvertible {
    var description: String {
        return root?.description ?? "empty tree"
    }
}
